%ordem de contrucao
%capa
%folha de rosto
%folha de aprovacao
%dedicatoria e agradecimentos
%resumo
%abstract
%sumario
%lista de figuras e tabelas
%lista de abreviaturas e siglas
%lista de simbolos

\documentclass{abnt}
%\documentclass{article}

\usepackage[utf8]{input enc}
\usepackage[brazil]{babel}
\usepackage[alf]{abntcite}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{tabularx}
\usepackage{longtable}
\usepackage{url}
\usepackage{tabela-simbolos}
\usepackage{booktabs}
\usepackage{listings}
\usepackage{graphics}
\usepackage{rotating}

\bibliographystyle{abnt-alf}

\titulo{Pycoopiler: Compilador para linguagem \emph{almostC} escrito em \emph{Python}}
\autor{André Felipe Santos \\
		Rodrigo Rodrigues da Silva}

\comentario{Relatório final do projeto de compilador da disciplina PCS2056 - Linguagens e Compiladores\\ \\ \emph{Prof. Dr. Ricardo Luis A. Rocha} }
\instituicao{Escola Politécnica da Universidade de São Paulo}
\local{São Paulo}
\data{2008}

\begin{document}

%\capa

\folhaderosto

%\sumario
\tableofcontents

\listoffigures

\listoftables


\chapter{Introdu\c{c}ão}\label{chap:introducao}
Este documento apresenta o projeto e desenvolvimento de um compilador\footnote{Disponível em http://rodrigopitanga.googlecode.com} para uma linguagem imperativa baseada na linguagem C. O compilador foi implementado na linguagem de programação interpretada \emph{Python}.

Apresentaremos uma definição formal da linguagem, posteriormente formalizada em notação de Wirth. Descreveremos as estruturas dos analisadores léxico e sintático, com os gráficos de seus autômatos, e faremos uma discussão sobre a análise semântica.

\chapter{Defini\c{c}ão}\label{chap:definicao}

\section{Defini\c{c}ão informal}
A linguagem de programação \emph{almostC} segue os principais conceitos da liguagem de programação \emph{C}, sendo um subconjunto muito simplificado de sua especificação \cite{especc}. Nossa linguagem apresenta recursos como declarações, chamada de funções com parâmetros, comandos de iteração \emph{if} e \emph{while}, funções $void$ e $int$ e vetores unidimensionais.

São palavras reservadas da linguagem: 
\begin {lstlisting}
	int void if while return 
\end{lstlisting}

A tabela \ref{tab:operadores} apresenta os operadores da linguagem. 

\begin{table}[htr!]\centering
\caption{Operadores da linguagem \emph{almostC}}\label{tab:operadores}
\begin{tabular}{cccccc}\hline
Tipos  & Operadores\\\hline
Aritméticos  & $+$  $-$  $*$  $\%$  $/$ \\\hline
Teste de igualdade  &  $==$  $!=$ \\\hline
Relações de ordem  &  $>$  $>=$  $<$  $<=$ \\\hline
Lógica booleana  &  !  \&  $|$ \\\hline
Atribuição  &  $=$ \\\hline
Referência  &  $[$  $]$    \\\hline
Sequência  &  $,$    \\\hline
\end{tabular}
\end{table}

Um programa em nossa linguagem será composto basicamente por funções. Cada função é composta por nome, tipo de retorno, parâmetros de entrada e um bloco de comandos. O bloco de comandos, por sua vez, é composto por declarações e por comandos. As declarações devem ser feitas no início do bloco, antes dos comandos. Os comandos podem ser atribuições, chamadas de função ou comandos \emph{if} e \emph{while} (desse modo, a linguagem definida é suficiente para escrever programas de acordo com o teorema de Böhm-Jacopini).
Nossa linguagem apresenta suporte a expressões aritméticas e lógicas\footnote{No entanto, não há tipo de dados booleano.}.
A linguagem também apresentará as funções de entrada e saída \emph{read} e \emph{print}. O código objeto de saída do compilador será código \emph{assembly} relocável para a Máquina de Von Neuman desenvolvida pelo PCS.

A listagem abaixo apresenta um exemplo de programa escrito em \emph{almostC}:

\lstinputlisting{exemplo1.ac}

\section{Defini\c{c}ão Formal}
Nesta seção apresentamos a definição da linguagem em notação de Wirth.

\lstinputlisting{Wirth.txt}

\chapter{Análise Léxica}\label{chap:lexico}
O analisador léxico é implementado através de um autômato finito determinístico. O autômato, por sua vez, é implementado em um laço \emph{while} com diversos \emph{if}s encadeados que testam cada estado. 

\section{Defini\c{c}ão Formal}
O analisador léxico reconhece as seguintes expressões, mapeando-as em \emph{tokens} da forma \textbf{$<$TIPO,CONTEÚDO$>$}:

\lstinputlisting{lexico.txt}

\section{Implementação e Testes}

O analisador sintático é implementado pela classe \emph{tokenizer.py}. A classe possui uma interface simples com o restante do código, bastando passar um arquivo de entrada contendo o código fonte na sua inicialização. A partir daí basta utilizar o método \textbf{next\_token\(\)} para avançar para o próximo token e acessar o membro \textbf{current} para acessar o token atual. Os testes foram feitos através da API de testes automatizados do Python e seu resultado segue no anexo \ref{an:lex}.

O analisador léxico foi implementado com base no autômato da figura \ref{fig:lexico}. Por clareza, as transições em vazio de cada estado de aceitação de volta ao estado inicial, devolvendo um token, foram omitidas.

\begin{sidewaysfigure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{lexico.png}
	\caption{Autômato do analisador léxico}
	\label{fig:lexico}
\end{sidewaysfigure}

\chapter{Análise Sintática}\label{chap:sintatica}

\section{Defini\c{c}ão Formal}

A definição da gramática em notação de Wirth foi simplificada de modo a obtermos um autômato de pilha estruturado. Os diagramas das sub-máquinas são apresentados abaixo:

\begin{figure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{program.png}
	\caption{Sub-máquina PROGRAM (Programa)}
	\label{fig:smprograma}
\end{figure}

\begin{figure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{decls.png}
	\caption{Sub-máquina DECLS (Declarações)}
	\label{fig:smdecls}
\end{figure}

\begin{figure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{largs.png}
	\caption{Sub-máquina L\_ARGS (Lista de Argumentos)}
	\label{fig:smargs}
\end{figure}

\begin{figure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{chfunc.png}
	\caption{Sub-máquina CH\_FUNC (Chamada de Função)}
	\label{fig:smchfunc}
\end{figure}

\begin{figure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{explog.png}
	\caption{Sub-máquina EXP\_LOG (Expressão Lógica)}
	\label{fig:smexplog}
\end{figure}
\begin{figure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{exparith.png}
	\caption{Sub-máquina EXP\_ARITH (Expressão Aritmética)}
	\label{fig:smexparith}
\end{figure}
\begin{figure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{ref.png}
	\caption{Sub-máquina REF (Referência)}
	\label{fig:smref}
\end{figure}
\begin{sidewaysfigure}[h]
	\centering
		\includegraphics[width=1.00\textwidth]{cmd.png}
	\caption{Sub-máquina CMDS (Comandos)}
	\label{fig:smcmd}
\end{sidewaysfigure}

\section{Implementa\c{c}ão e Testes}

Assim como no analisador léxico, realizamos testes automatizados com o analisador sintático. Durante os testes, corrigimos algumas inconsistências encontradas na linguagem e nos autômatos, como a impossibilidade de chamada de uma função sem argumentos. Os testes seguem no anexo \ref{an:sint}. Os arquivos de entrada utilizados nos testes seguem anexo a este relatório, junto com o código fonte dos analisadores.

\chapter{Análise Semântica}\label{chap:semantico}

A análise semântica foi realizada através de dois módulos:
\textbf{semantico.py} e \textbf{codegen.py}. O primeiro lida com o conjunto de
ações semânticas a serem executadas nas transições do analisador sintático, e o
segundo, com as rotinas de geração de código. A linguagem de nosso código
objeto é a linguagem de montador (\emph{assembly}) da MVN.

As ações semânticas tomadas por modelo foram as mesmas do livro
\emph{Introdução à compilação} de João José Neto. Por fim, conseguimos
implementar as ações relativas a expressões aritméticas, obtendo resultados
bem satisfatórios, obedecendo precedência e o aninhamento de expressões
através de parênteses, conseguindo converter uma expressão válida em C para a
linguagem de destino com sucesso.

\section{Implementa\c{c}ão e Testes}

A classe \emph{semantico} utiliza, como dito anteriormente, as ações semânticas
especificadas na obra citada. Para a implementação destas ações, utilizamos
duas listas de Python, cujo comportamento pode simular por completo uma pilha,
para fazer o papel das pilhas de operadores e operandos conforme especificado.
Tomamos a especificação à risca, inclusive utilizando da recursão quando a
mesma foi solicitada.

A classe \emph{codegen} lida justamente com a geração de código propriamente
dita. A idéia envolve, conforme as ações semânticas ocorrem com as transições do
analisador sintático, adicionar trechos de código de operações da MVN e os
devidos identificadores correspondentes aos endereços de memória alvo.

Para facilitar a geração de código, decidimos por fazer duas grandes strings
que juntas formam o código objeto final: a área de código, que utiliza rótulos
para as variáveis e constantes; e a área de dados, onde os dados relativos a
esses rótulos são armazenados. Esta técnica torna a geração mais simples por
não termos tanto problema quanto à relocação: seja a quantidade de dados
envolvida, a área de programa não vai mudar muito, nem a área de dados será
muito deslocada.

Quanto à tabela de símbolos (classe \emph{symbtable}, módulo
\textbf{symbtable.py}), utilizamos um dicionário da linguagem Python. Esta
estrutura, diferentemente da lista, possui uma peculiaridade: suas entradas
individuais não estão organizadas através de um índice, mas sim através de
\textbf{chaves}, que são quaisquer valores imutáveis em Python, como strings
ou t-uplas. Assim sendo, nossa tabela possui como chave o nome do símbolo como
ele aparece no código fonte e, como valores, o rótulo que será usado na
linguagem objeto e sua posição na tabela. A tabela possui também um atributo de
escopo, para identificar qual é o mesmo que está sendo apresentado ali.

Para o nome interno de variáveis, decidimos simplesmente utilizar
``\textbf{VAR}'' concatenado à posição na tabela de símbolos. O mesmo
procedimento é usado para se obter os nomes temporários para a geração de
código para as expressões aritméticas.

Os testes realizados, novamente com a API de testes de unidade do Python,
apresentaram bom resultado, podem ser conferidos no apêndice \ref{an:sem}.

\appendix

\chapter{Resultado dos testes do analisador léxico}\label{an:lex}

\lstinputlisting{testetokenizer.txt}

\chapter{Resultado dos testes do analisador sintático}\label{an:sint}

\lstinputlisting{testesintatico.txt}

\chapter{Resultado dos testse da geração de código}\label{an:sem}

\lstinputlisting{testesemantico.txt}

\end{document}